package 笔试题;

import java.util.Arrays;

public class lk_1883 {

    static long mmm = 0;
    static long mmm2 = 0;
    static long mmm3 = 0;
    static long mmm4 = 0;
    static long mmm5 = 0;

    public static void main(String[] args) {
        long l = System.currentTimeMillis();
        System.out.println(combinationSum4(new int[]{10,20,30,40,50,60,70,80,90,100,110,120,130,140,150,160,170,180,190,200,210,220,230,240,250,260,270,280,290,300,310,320,330,340,350,360,370,380,390,400,410,420,430,440,450,460,470,480,490,500,510,520,530,540,550,560,570,580,590,600,610,620,630,640,650,660,670,680,690,700,710,720,730,740,750,760,770,780,790,800,810,820,830,840,850,860,870,880,890,900,910,920,930,940,950,960,970,980,990,111}, 999));
        long l2 = System.currentTimeMillis();
        System.out.println("总时间:" + (l2-l));
        System.out.println("次数：" + mmm);
        System.out.println("次数2：" + mmm2);
        System.out.println("次数3：" + mmm3);
        System.out.println("次数4：" + mmm4);
        System.out.println("次数5：" + mmm5);

    }
    public static int combinationSum4(int[] nums, int target) {
        Arrays.sort(nums);
        return db(nums,target,0,0);
    }

    //n :到哪一位了          m：占用多少位了
    public static int db(int[] nums, int target,int n,int m){
        if(n == nums.length){
            return 0;
        }
        if(target<nums[n]){
            return 0;
        }
        if(target==nums[n]){
            return m+1;
        }

        int re = 0;
        int x;
        int k=target/nums[n];
        for (int j=k;j>=0;j--){
            int t = target-nums[n]*j;
            if(t == 0){
                mmm2++;
                re += db(m+j,j);
            }else{
                mmm++;
                x = db(nums,t,n+1,m+j);
                if(x == 0){
                    mmm3++;
                }else if(j == 0){
                    re += x;
                    mmm4++;
                }else{
                    mmm5++;
                    re += (x * db(m+j,j));
                }
            }
        }
        return re;
    }

    public static int db(int w,int j){
        if(j == 0){
            return 0;
        }
        if(w == j){
            return 1;
        }
        long s = 1;
        long ss = 1;
        for (int i=1;i<=j;i++){
            s *= (w-i+1);
            ss *= i;
        }
        return (int) (s/ss);
    }

}
